#ifndef APP_ALGORITHM_DYNAMIC_PROGRAMMING_INCLUDE_DYNAMIC_PROGRAMMING_H
#define APP_ALGORITHM_DYNAMIC_PROGRAMMING_INCLUDE_DYNAMIC_PROGRAMMING_H

#include <iostream>
#include <vector>

class IDynamicProgramming {
public:
    virtual ~IDynamicProgramming() = default;
    IDynamicProgramming(const char* desc) : descriptor_(desc) {}
    virtual void Executor();
    virtual int32_t ClimbStairs(uint32_t stairFloors) = 0;
protected:
    const char* descriptor_ = "IDynamicProgramming";
};

class ViolentRecursion : public IDynamicProgramming {
public:
    ViolentRecursion() : IDynamicProgramming("暴力递归算法") {}
    int32_t ClimbStairs(uint32_t stairFloors) override;
};

class MemoryBasedSearch : public IDynamicProgramming {
public:
    MemoryBasedSearch() : IDynamicProgramming("记忆化搜索算法") {}
    int32_t ClimbStairs(uint32_t stairFloors) override;
private:
    int32_t Dfs(uint32_t stairFloors, std::vector<int32_t> &memo);
};

class DynamicProgramming : public IDynamicProgramming {
public:
    DynamicProgramming() : IDynamicProgramming("动态规划算法") {}
    int32_t ClimbStairs(uint32_t stairFloors) override;
};

class PerfDynamicProgramming : public IDynamicProgramming {
public:
    PerfDynamicProgramming() : IDynamicProgramming("空间优化版动态规划算法") {}
    int32_t ClimbStairs(uint32_t stairFloors) override;
};
#endif // APP_ALGORITHM_DYNAMIC_PROGRAMMING_INCLUDE_DYNAMIC_PROGRAMMING_H